﻿/*
题目: 计算右侧小于当前元素的个数

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。

https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

/*
* 计算右侧元素
* [x y z]  [i j k]
* 在归并中，如果 x < j ，那么说明 j 前面的元素都是 < x 的，也就是符合小于 x 的右侧元素
* 所以 x += j - LEFT_START
* 但是由于记不住原来数组元素的下标，所以这里需要对 索引数组 进行排序，方便定位
*/
class Solution {
public:
    vector<int> res;
    vector<int> index;    // 索引数组，对索引进行排序

    vector<int> countSmaller(vector<int>& nums) {
        res = vector<int>(nums.size(), 0);
        for (int i = 0; i < nums.size(); i++)  index.emplace_back(i);

        // 计算每个元素在排好序之后的正确位置和原来的位置的差值
        // 为了方便得到原来的数据的位置，所以需要使用索引排序
        merge_sort(nums, index, 0, index.size() - 1);

        return res;
    }

    void merge_sort(vector<int>& nums, vector<int>& index, int left, int right) {
        if (left >= right)  return;

        int mid = left + ((right - left) >> 1);
        merge_sort(nums, index, left, mid);
        merge_sort(nums, index, mid + 1, right);

        merge(nums, index, left, mid, right);
    }

    void merge(const vector<int>& nums, vector<int>& index, int left, int mid, int right) {
        int s1 = left, s2 = mid + 1;
        int e1 = mid, e2 = right;

        vector<int> tmp(right - left + 1);
        int k = 0;
        while (s1 <= e1 && s2 <= e2) {
            if (nums[index[s1]] <= nums[index[s2]]) {
                tmp[k++] = index[s1];
                res[index[s1]] += s2 - mid - 1;
                s1++;
            }
            else {
                tmp[k++] = index[s2];
                s2++;
            }
        }

        while (s1 <= e1) {
            tmp[k++] = index[s1];
            res[index[s1]] += s2 - mid - 1;
            s1++;
        }

        while (s2 <= e2) {
            tmp[k++] = index[s2];
            s2++;
        }

        for (int i = 0; i < k; i++) {
            index[i + left] = tmp[i];
        }
    }
};